// https://leetcode-cn.com/problems/subsets/
// 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
// 输入：nums = [1,2,3]
// 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
// 【这题存在特殊性：求所有数的集合】
#include <iostream>
#include <vector>
#include <bitset>

using namespace std;

class Solution {
public:
	// 动态规划 基础思想就是新的集合 = 原集合 + (原集合的每个元素+新的元素) + 新的元素
	// 1 
	// 1 2 1,2
	// 1 2 1,2 3 1,3 2,3 1,2,3 
	vector<vector<int>> subsets1(vector<int>& nums) {
		int len = nums.size();
		vector<vector<int>> res;
		res.push_back({});
		for(int i = 0; i < len; i++){
			int size = res.size();
			for(int j = 0; j < size; j++){
				vector<int> tmp = res[j];
				tmp.push_back(nums[i]);
				res.push_back(tmp);
			}
		}
		return res;
    }
};

int main(){
	vector<int> nums = {1,2,3};
	Solution so;
	auto res = so.subsets1(nums);
	
	cout << "show:" << endl;
	for(auto item : res){
		for(auto i : item){
			cout << i << ",";
		}
		cout << endl;
	}
	
	return 1;
}